#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/12/10 11:35|11:35
# @Author  : yangdingyi
# @File    : 第K个语法符号
# @Software: PyCharm


class Solution:
    def kthGrammar(self, N: int, K: int) -> int:

        def work(key: int, k: int, w: int, dep: int, n: int) -> int:
            if n == dep:
                return key
            w //= 2
            keys = [0, 1] if key == 0 else [1, 0]
            key = keys[0] if k <= w else keys[1]
            return work(key, k-w if k > w else k, w, dep+1, n)

        return work(0, K, 2**(N-1), 1, N)


solve = Solution()

questions = [
    (1, 1),
    (2, 1),
    (2, 2),
    (4, 5),
    (3, 2)
]

for i, q in enumerate(questions):
    N, K = q
    print('question[#{}]: N = {}, K = {}'.format(i, N, K))
    print('ans:', solve.kthGrammar(N, K))
